#include <iostream>
#include <algorithm>
#include <string>
#include <ctime>
#include <vector>
#include <iterator>
#include "../../source/search/find.h"

const int DEFAULT_CNT = 10;

int gen_nums(int argc, char ** argv, std::vector<int> & nums)
{
    int cnt = DEFAULT_CNT;
    if(argc == 2)
    {
        cnt = std::atoi(argv[1]);
    }
    if(argc < 3)
    {
        srand(time(NULL));
        int up_bound = (100 < cnt) ? cnt*10 : 1000;
        for(int i = 0; i < cnt; ++ i)
        {
            nums.push_back(rand() % up_bound);
        }
    }
    else
    {
        for(int i = 1; i < argc; ++ i)
        {
            nums.push_back(std::atoi(argv[i]));
        }
    }
    return cnt;
}

template <typename T>
inline void print(T t)
{
    std::cout << t << " ";
}

template <typename T>
void disp_vector(std::vector<T> & v, const char * description)
{
    std::cout << description << std::endl;
    typename std::vector<T>::iterator it;
    it = v.begin();
    if(v.size() > 20)
    {
        it += 20;
        std::for_each(v.begin(), it, print<T>);
        std::cout << "...";
    }
    else
    {
        std::for_each(v.begin(), v.end(), print<T>);
    }
    std::cout << std::endl << std::endl;
}

extern inline void swap(int nums[], int pos1, int pos2);

int main(int argc, char ** argv)
{
    std::vector<int> nums;
    std::vector<int> seconds;
    int start_time = 0;
    int pos = -1;

    gen_nums(argc, argv, nums);
    std::sort(nums.begin(), nums.end());
    disp_vector<int>(nums, "Sequence:");
    
    int target;
    char ch;
    std::cout << "Input a number to find?\n>> ";
    std::cin >> ch;
    if(ch != 'y')
    {
        int target_index = rand() % nums.size();
        target = nums[target_index];
        std::cout << "Target to find: " << target << " at index " 
            << target_index << std::endl << std::endl;
        
    }
    else
    {
        std::cout << ">> ";
        std::cin >> target;
    }
    
    start_time = time(NULL);
    pos = find(target, &(nums.at(0)), 0, nums.size() - 1);
    seconds.push_back(std::time(NULL) - start_time);
    std::cout << "Binary search: " << pos << std::endl;

    start_time = time(NULL);
    pos = find_first_basic(target, &(nums.at(0)), nums.size());
    seconds.push_back(std::time(NULL) - start_time);
    std::cout << "Linear search: " << pos << std::endl;
    
    disp_vector(seconds, "Time used for each:");
    return 0;
}

